package day04

import "sort"

// day04
//
// 435. 无重叠区间
//
// https://leetcode.cn/problems/non-overlapping-intervals/
//
// ```go
func eraseOverlapIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	cnt := 0
	for i := 1; i < len(intervals); i++ {
		r := intervals[i-1][1]
		l := intervals[i][0]
		if r > l {
			intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
			cnt++
		}
	}
	return cnt
}
func max(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// ```
//
// 763. 划分字母区间
//
// https://leetcode.cn/problems/partition-labels/
//
// ```go
func partitionLabels(s string) []int {
	mp := map[byte]int{}
	str := []byte(s)
	for idx, v := range s {
		ch := byte(v)
		mp[ch] = idx
	}
	startIdx, endIdx := 0, 0
	ans := make([]int, 0)
	curIdx := mp[str[0]]
	for i := 0; i < len(str); i++ {
		curIdx = max(curIdx, mp[str[i]])
		if i == curIdx {
			endIdx = curIdx
			ans = append(ans, endIdx-startIdx+1)
			startIdx = curIdx + 1
		}
	}
	return ans
}

//```

// 56. 合并区间
//
// https://leetcode.cn/problems/merge-intervals/
//
// ```go
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	l, r := intervals[0][0], intervals[0][1]
	ans := make([][]int, 0)
	for i := 1; i < len(intervals); i++ {
		if r >= intervals[i][0] {
			r = max(r, intervals[i][1])
		} else {
			ans = append(ans, []int{l, r})
			l, r = intervals[i][0], intervals[i][1]
		}
	}
	ans = append(ans, []int{l, r})
	return ans
}

//```
